//Thursday, December 17 2009
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class DonutsOnTheGrid
{
public:
	long long calc(int H, int W, int seed, int threshold)
	{
		//vector<vector<long long> > v(H, vector<long long> (W, 0));
		vector<string> donut(H, string(W, '.'));
		//v[0][0] = seed;
		long long x = seed;
		for(int i=0; i<H; i++)
		{
			for(int j=0; j<W; j++)
			{
				x = (x * 25173 + 13849) % 65536;
				if(x < threshold)
					donut[i][j] = '0';
			}
		}
// 		for(int i=0; i<H; i++)
// 		{
// 			for(int j=0; j<W; j++)
// 			{
// 				cout << donut[i][j] << ", ";
// 			}
// 			cout << endl;
// 		}
		long long ret = 0;
		static bool dp[351][351][351];
		//row, col_begin, col_end;
		memset(dp, false, sizeof(dp));
		for(int i=0; i<H; i++)
		{
			for(int j=0; j<W; j++)
			{
				if(donut[i][j] == '0')
					dp[i][j][j] = true;
				for(int idx=j+1; idx<W; idx++)
				{
					if(donut[i][idx]=='0' && dp[i][j][idx-1])
						dp[i][j][idx] = true;
				}
			}
		}
		for(int i=0; i<W; i++)
		{
			for(int j=i+2; j<W; j++)
			{
				int score = 0;
				for(int k=2; k<H; k++)
				{
					if(dp[k-2][i][j])
						score++;
// 					cout << donut[k-1][i] << ", " << donut[k-1][j] << endl;
					if(donut[k-1][i]!='0' || donut[k-1][j]!='0')
						score = 0;
					if(dp[k][i][j])
						ret += score;
				}
			}
		}
		return ret;
	}
};
//kusano;